package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class Q140ii {

    /**
     * @param a: A 32bit integer
     * @param b: A 32bit integer
     * @param n: A 32bit integer
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
    	if (b == 1) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        a = a % b;
        List<Integer> list = new ArrayList<>();
        list.add(a);
        for(int i = 2; i <= n; i++) {
        	int c = (list.get(list.size() - 1) * a )% b;
        	if(list.contains(c)) {
        		break;
        	}else {
        		list.add(c);
        	}
        }
        int t = n % list.size();
        return list.get(t);
    }
    @Test
    public void testA() {
        // 2, 2147483647, 2147483647
        // 109, 10000007, 1000001
        // System.out.println(fastPower(2, 2147483647, 2147483647));
        System.out.println(fastPower(109, 10000007, 1000001));
    }

}
